Field
The described embodiments relate to techniques for performing a query of a database. More specifically, the described embodiments relate to techniques for communicating messages about queries and partial query results among shards in a graph database.
Related Art
Data associated with applications is often organized and stored in databases. Large databases are often subdivided into ‘shards,’ which contain subsets of the data. In principle, this architecture allows large databases to be implemented on multiple systems and/or may allow queries from the applications to be executed by the shards in parallel, which can reduce the time needed to obtain the query results.
In practice, such parallel execution of queries can be complicated. For example, information and decision-making about where data is stored in a distributed database may, in turn, need to be distributed. In particular, a client that is executing an application may need to have access to, or the ability to access, information about the structure of the distributed database, such as a global index that specifies which shards store desired information, so that the client can provide necessary queries to these shards. Alternatively or additionally, the shards may need to have access to, or the ability to access, the information about the structure of the distributed database, so that, when a shard receives a query for desired information that, at least in part, is stored in one or more other shards, the shard can forward the query to the appropriate shards.
Moreover, there may be considerable overhead associated with maintaining the information about the structure of the distributed database, as well as considerable overhead and complexity associated with the multiple messages exchanged with the client and among the shards in the distributed database. For example, whenever data is stored or updated in a particular shard, the information about the structure of the distributed database may need to be communicated using update messages within the distributed database and/or with clients. Similarly, if a query response from a shard only includes partial results, the partial results or information specifying the partial results may need to be included in messages when the initial query is forwarded within the distributed database. These messages may consume significant capacity and processing capability within the distributed database and/or within the clients. Consequently, the use of shards in a database may not provide all of the advantages it is supposed to and, in the worst case, can degrade performance and the user experience when using the associated application(s).
Table 1 provides an edge query in accordance with an embodiment of the present disclosure.
Table 2 provides data in JavaScript Object Notation (JSON) in accordance with an embodiment of the present disclosure.
Table 3 provides an edge query in accordance with an embodiment of the present disclosure.
Table 4 provides a result for an edge query in accordance with an embodiment of the present disclosure.
Note that like reference numerals refer to corresponding parts throughout the drawings. Moreover, multiple instances of the same part are designated by a common prefix separated from an instance number by a dash.